//seamCarver是一种内容感知型(content-aware)图像大小调整技术,
//与标准的与内容无关的大小调整技术（例如裁剪和缩放）不同，接缝雕刻保留了图像中最有趣的特征（长宽比、存在的对象集等）。
//坐标，和颜色组成……
//用双梯度能量函数计算能量
//接缝识别，找到总能量最小的垂直接缝。这类似于边加权有向图中的经典最短路径问题，但有以下几点不同：
//权重在顶点上，而不是边上。
//我们想要找到从顶行任意W 个像素到底行 任意W个像素的最短路径。
//该有向图是非循环的，其中存在从像素 ( x , y ) 到像素 ( x − 1, y + 1)、( x , y + 1) 和 ( x + 1, y + 1) 的向下边，假设坐标在规定的范围内。
//接缝去除。 最后一步是从图像中删除接缝处的所有像素
//Your code should throw an IllegalArgumentException when a constructor or method is called with an invalid argument, as documented below
//按照惯例，索引x和y分别是 0 到width − 1 和 0 到height − 1之间的整数，其中width是当前图像的宽度，height 是高度
//如果构造函数 removeVerticalSeam()、或removeHorizontalSeam()使用空参数调用
// if removeVerticalSeam() is called when the width of the picture is less than or equal to 1 
//or if removeHorizontalSeam() is called when the height of the picture is less than or equal to 1.
//构造函数：
//The data type may not mutate the Picture argument to the constructor.
//计算能量：
import java.awt.Color;

import edu.princeton.cs.algs4.Picture;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stopwatch;

public class SeamCarver {
  private Picture picture;
  private double[][] energy;

  // create a seam carver object based on the given picture
  public SeamCarver(Picture picture) {
    if (picture == null) {
      throw new IllegalArgumentException("picture不能为空！");
    }
    this.picture = new Picture(picture);
    energy = new double[picture.height()][picture.width()];
    for (int i = 0; i < picture.height(); i++) {
      for (int j = 0; j < picture.width(); j++) {
        energy[i][j] = energy(j, i);
      }
    }
  }

  // current picture
  public Picture picture() {
    return picture;
  }

  // width of current picture
  public int width() {
    return picture.width();
  }

  // height of current picture
  public int height() {
    return picture.height();
  }

  // energy of pixel at column x and row y
  public double energy(int x, int y) {
    if (x < 0 || x > width() - 1 || y < 0 || y > height() - 1) {
      throw new IllegalArgumentException("x,y不在范围内！");
    }
    if (x == 0 || x == picture.width() - 1 || y == 0 || y == picture.height() - 1) {
      double result = 1000.0;
      return result;
    }
    Color color_x1 = picture.get(x - 1, y);
    Color color_x2 = picture.get(x + 1, y);
    Color color_y1 = picture.get(x, y - 1);
    Color color_y2 = picture.get(x, y + 1);
    double Rx_2 = Math.pow(color_x2.getRed() - color_x1.getRed(), 2);
    double Ry_2 = Math.pow(color_y2.getRed() - color_y1.getRed(), 2);
    double Gx_2 = Math.pow(color_x2.getGreen() - color_x1.getGreen(), 2);
    double Gy_2 = Math.pow(color_y2.getGreen() - color_y1.getGreen(), 2);
    double Bx_2 = Math.pow(color_x2.getBlue() - color_x1.getBlue(), 2);
    double By_2 = Math.pow(color_y2.getBlue() - color_y1.getBlue(), 2);

    double result = +Math.sqrt(Rx_2 + Ry_2 + Gx_2 + Gy_2 + Bx_2 + By_2);
    return result;
  }

  // sequence of indices for horizontal seam
  // 水平接缝
  // 思路是这样的，一个正常范围内的点，可以由三条路径而来，我们判断哪条路径是到他的最短路径，然后保存那条路径到他的距离以及路径。
  public int[] findHorizontalSeam() {
    int[][] edgeTo = new int[height()][width()];
    double[][] dis = new double[height()][width()];
    for (int i = 0; i < width(); i++) // 列循环
    {
      for (int j = 0; j < height(); j++) // 行循环
      {
        if (i == 0) {
          edgeTo[j][i] = j;
          dis[j][i] = energy[j][i];
          continue;
        }
        double up, equal = dis[j][i - 1], down;
        if (j == 0) {
          up = Double.POSITIVE_INFINITY;
        } else {
          up = dis[j - 1][i - 1];
        }
        if (j == height() - 1) {
          down = Double.POSITIVE_INFINITY;
        } else {
          down = dis[j + 1][i - 1];
        }
        int min;
        if (Double.compare(up, equal) > 0) {
          min = j;
          if (Double.compare(equal, down) > 0) {
            min = j + 1;
          }
        } else {
          min = j - 1;
          if (Double.compare(up, down) > 0) {
            min = j + 1;
          }
        }
        dis[j][i] = dis[min][i - 1] + energy(i, j);
        edgeTo[j][i] = min;
      }
    }

    // 找到最短路径中，最后的那个点
    int min = 0;
    for (int j = 0; j < height() - 1; j++) // 对最后一列中，行进行循环
    {
      if (Double.compare(dis[min][width() - 1], dis[j][width() - 1]) > 0) {
        min = j;
      }
    }

    // 对每一列进行遍历得到最短路径
    int[] result = new int[width()];
    for (int i = width() - 1; i >= 0; i--) {
      if (i == width() - 1) {
        result[i] = min;
        continue;
      }
      result[i] = edgeTo[result[i + 1]][i + 1];
    }
    return result;
  }

  // sequence of indices for vertical seam
  // 垂直接缝
  public int[] findVerticalSeam() {
    int[][] edgeTo = new int[height()][width()];
    double[][] dis = new double[height()][width()];
    for (int j = 0; j < height(); j++) // 行循环
    {
      for (int i = 0; i < width(); i++) // 列循环
      {
        if (j == 0) {
          edgeTo[j][i] = i;
          dis[j][i] = energy[j][i];
          continue;
        }
        double left, equal = dis[j - 1][i], right;
        if (i == 0) {
          left = Double.POSITIVE_INFINITY;
        } else {
          left = dis[j - 1][i - 1];
        }
        if (i == width() - 1) {
          right = Double.POSITIVE_INFINITY;
        } else {
          right = dis[j - 1][i + 1];
        }
        int min;
        if (Double.compare(left, equal) > 0) {
          min = i;
          if (Double.compare(equal, right) > 0) {
            min = i + 1;
          }
        } else {
          min = i - 1;
          if (Double.compare(left, right) > 0) {
            min = i + 1;
          }
        }
        dis[j][i] = dis[j - 1][min] + energy(i, j);
        edgeTo[j][i] = min;
      }
    }

    // 找到最短路径中，最后的那个点
    int min = 0;
    for (int j = 1; j < width() - 1; j++) // 对最后一行中，列进行循环
    {
      if (Double.compare(dis[height() - 1][min], dis[height() - 1][j]) > 0) {
        min = j;
      }
    }

    // 对每一行进行遍历得到最短路径
    int[] result = new int[height()];
    for (int i = height() - 1; i >= 0; i--) {
      if (i == height() - 1) {
        result[i] = min;
        continue;
      }
      result[i] = edgeTo[i + 1][result[i + 1]];
    }
    return result;
  }

  // remove horizontal seam from current picture
  // 水平接缝
  public void removeHorizontalSeam(int[] seam) {
    if (seam == null) {
      throw new IllegalArgumentException("seam不能为空！");
    }
    if (picture.height() <= 1) {
      throw new IllegalArgumentException("picture too small");
    }
    Picture newPicture = new Picture(picture.width(), picture.height() - 1);
    for (int col = 0; col < picture.width(); col++) { // 列循环
      for (int row = 0; row < picture.height(); row++) { // 行循环
        Color color = picture.get(col, row);
        if (row < seam[col]) {
          newPicture.set(col, row, color);
        } else if (row == seam[col]) {
          continue;
        } else {
          newPicture.set(col, row - 1, color);
        }
      }
    }
    picture = newPicture;
    energy = new double[picture.height()][picture.width()];
    for (int i = 0; i < picture.height(); i++) {
      for (int j = 0; j < picture.width(); j++) {
        energy[i][j] = energy(j, i);
      }
    }
  }

  // remove vertical seam from current picture
  // 垂直接缝
  public void removeVerticalSeam(int[] seam) {
    if (seam == null) {
      throw new IllegalArgumentException("seam不能为空！");
    }
    if (picture.width() <= 1) {
      throw new IllegalArgumentException("picture too small");
    }
    Picture newPicture = new Picture(picture.width() - 1, picture.height());
    for (int row = 0; row < picture.height(); row++) { // 行循环
      for (int col = 0; col < picture.width(); col++) { // 列循环
        Color color = picture.get(col, row);
        if (col < seam[row]) {
          newPicture.set(col, row, color);
        } else if (col == seam[row]) {
          continue;
        } else {
          newPicture.set(col - 1, row, color);
        }
      }
    }
    picture = newPicture;
    energy = new double[picture.height()][picture.width()];
    for (int i = 0; i < picture.height(); i++) {
      for (int j = 0; j < picture.width(); j++) {
        energy[i][j] = energy(j, i);
      }
    }
  }

  // unit testing (optional)
  public static void main(String[] args) {
    Picture inputImg = new Picture("3.png");
    int removeColumns = Integer.parseInt("1");
    int removeRows = Integer.parseInt("0");

    StdOut.printf("image is %d columns by %d rows\n", inputImg.width(), inputImg.height());
    SeamCarver sc = new SeamCarver(inputImg);

    Stopwatch sw = new Stopwatch();
    for (int row = 0; row < sc.height(); row++) {
      for (int col = 0; col < sc.width(); col++)
        StdOut.printf("%9.0f ", sc.energy(col, row));
      StdOut.println();
    }

    for (int i = 0; i < removeRows; i++) {
      int[] horizontalSeam = sc.findHorizontalSeam();
      // for(int ap=0;ap<horizontalSeam.length;ap++)
      // {
      // System.out.println(horizontalSeam[ap]);
      // }
      sc.removeHorizontalSeam(horizontalSeam);
    }

    for (int i = 0; i < removeColumns; i++) {
      int[] verticalSeam = sc.findVerticalSeam();
      for (int ap = 0; ap < verticalSeam.length; ap++) {
        System.out.println(verticalSeam[ap]);
      }
      sc.removeVerticalSeam(verticalSeam);
    }
    Picture outputImg = sc.picture();

    StdOut.printf("new image size is %d columns by %d rows\n", sc.width(), sc.height());

    StdOut.println("Resizing time: " + sw.elapsedTime() + " seconds.");
    SeamCarver b = new SeamCarver(outputImg);
  }
}
